package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.ListNode;
import com.leetcode.common.utils.ListNodeUtils;

/**
 * @author 覃国强
 * @date 2022-06-30 16:14
 */
public class 题库_0148_排序链表 {

  public static void main(String[] args) {
    ListNode head = ListNodeUtils.generateListNode(new int[]{4, 2, 1, 3});
    ListNodeUtils.print(head);
    Solution solution = new Solution();
    ListNode sortList = solution.sortList(head);
    ListNodeUtils.print(sortList);
  }

  static
  class Solution {
    public ListNode sortList(ListNode head) {
      if (head == null) {
        return head;
      }
      return mergeSort(head);
    }

    public ListNode mergeSort(ListNode head) {
      if (head.next != null) {
        ListNode rightHead = splitListNode(head);

//        System.out.print("head: ");
//        ListNodeUtils.print(head);
//        System.out.print("rightHead: ");
//        ListNodeUtils.print(rightHead);
//        System.out.println();

        head = mergeSort(head);
        rightHead = mergeSort(rightHead);
        return merge(head, rightHead);
      }
      return head;
    }

    private ListNode splitListNode(ListNode head) {
      ListNode slower = head;
      ListNode faster = head.next;
      while (faster != null && faster.next != null) {
        slower = slower.next;
        faster = faster.next.next;
      }

      // 将链表一拆为二
      ListNode rightHead = slower.next;
      slower.next = null;

      return rightHead;
    }

    private ListNode merge(ListNode left, ListNode right) {
      ListNode dummy = new ListNode();
      ListNode head = dummy;
      while (left != null && right != null) {
        if (left.val < right.val) {
          head.next = left;
          left = left.next;
        } else {
          head.next = right;
          right = right.next;
        }
        head = head.next;
      }
      head.next = left != null ? left : right;
      return dummy.next;
    }

  }

}
